// 二项队列

template <typename Comparable>
class BinomialQueue
{
private:
    struct BinomialNode
    {
        // 值
        Comparable element;
        // 左儿子
        BinomialNode* leftChild;
        // 右兄弟
        BinomialNode* nextSibling;
        // 构造函数
        BinomialNode(const Comparable & e, BinomialNode* lt, BinomialNode* rt) : element{e}, leftChild{lt}, nextSibling{rt} {}
        {
            
        }
    };
    // 默认的树数量
    const static int DEFAULT_TREES = 1;

    // 各个树的根节点组成的向量
    vector<BinomialNode *> theTrees;
    // 优先队列中的项数
    int currentSize;
    // 寻找最小节点
    int findMinIndex() const
    {
        int i;
        int minIndex;

        for(i=0; theTrees[i] == nullptr; ++i)
            // 本循环只是为了将i设置到底层，相当于一个简单的递归赋值
        /* 在底层遍历，持续判断最小值与空值，最后返回索引 */
        for(minIndex = i; i<theTrees.size(); ++i)
            if( theTrees[i] != nullptr &&
                theTrees[i]->element < theTrees[minIndex]->element)
                minIndex = 1;

        return minIndex;
    }
    // 返回队列最大容量
    int capacity() const
    /* 合并优先队列中的两个二项树 */
    BinomialNode* combineTrees(BinomialNode* t1, BinomialNode* t2)
    {
        if(t2->element < t1->element)
            return combineTrees(t2,t1);
        t2->nextSibling = t1->leftChild;
        t1->leftChild = t2;
        return t1;
    }
    void makeEmpty(BinomialNode*& t)
    BinomialNode* clone(BinomialNode* t) const


public:
    BinomialQueue()
    BinomialQueue(const Comparable & item)
    BinomialQueue(const BinomialQueue & rhs)
    BinomialQueue(BinomialQueue && rhs)

    ~BinomialQueue()

    BinomialQueue & operator=(const BinomialQueue & rhs)
    BinomialQueue & operator=(BinomialQueue && rhs)

    bool isEmpty()
    const Comparable & findMin() const

    void insert(const Comparable & x)
    void insert(Comparable && x)
    void deleteMin()
    /*  删除最小元
      * 1. 找出含有最小元素的树Bk，将其删除形成H'
      * 2. 在Bk中删除根，出现k-1个二项树，形成H''
      * 3. 将H'和H''合并
     */
    void deleteMin(Comparable & minItem)
    {
        // 判空
        if(isEmpty())
            throw UnderflowException {};

        // 找到最小元与其索引
        int minIndex = findMinIndex();
        minItem = theTrees[minIndex]->element;

        // 将最小元设置为根节点，存储最小元的左子树，删除根节点
        BinomialNode* oldRoot = theTrees[minIndex];
        BinomialNode* deletedTree = oldRoot->leftChild;
        delete oldRoot;

        /* 构建H'' */
        // 初始化一个优先队列
        BinomialQueue deletedQueue;
        // 设置它的树数量与节点数量
        deletedQueue.theTrees.resize(minIndex + 1);
        deletedQueue.currentSize = (1 << minIndex) - 1;
        // 遍历赋值
        for(int j = minIndex-1; j>=0; --j)
        {
            deletedQueue.theTrees[j] = deletedTree;
            deletedTree = deletedTree->nextSibling;
            deletedQueue.theTrees[j]->nextSibling = nullptr;
        }

        // 构建H'
        theTrees[minIndex] = nullptr;
        currentSize -= deletedQueue.currentSize + 1;

        merge(deletedQueue);
    }

    void makeEmpty()

    /* 将另一个优先队列H2并入H1中，H1是this，H2是rhs */
    void merge(BinomialQueue & rhs)
    {
        // 避免别名问题（要合并的优先队列与本队列同名）
        if(this == &rhs)
            return;
        // 由于是简单的合并，所以直接简单相加来更新队列尺寸
        currentSize += rsh.currentSize;

        // 若超过最大容量，则重构二项队列
        if(currentSize > capacity())
        {
            int oldNumTrees = theTrees.size();
            int newNumTrees = max(theTrees.size(),rhs.theTrees.size()) - 1;
            theTrees.resize(newNumTrees);
            for(int i = oldNumTrees; i < newNumTrees; ++i)
                theTrees[i] = nullptr;
        }
        
        // carry是从上一步迭代后的结果树，在这里先初始化
        BinomialNode* carry = nullptr;
        /* 
          * i是迭代次数，j是二叉树的满溢层数
          *
        */
        for(int i = 0, j=1; j<=currentSize; ++i,j*=2)
        {
            /* t1代表this的当前树的根节点，可能为空 */
            BinomialNode* t1 = theTrees[i];
            /* t2代表rhs的当前树的根节点，可能为空 */
            BinomialNode* t2 = (i < rhs.theTrees.size() ? rhs.theTrees[i] : nullptr);

            /* 讨论情况的判断数， */
            int whichCase = (t1 == nullptr ? 0 : 1);
            whichCase += (t2 == nullptr ? 0 : 2);
            whichCase += (carry == nullptr ? 0 : 4);

            switch (whichCase)
            {
            case 0: // 两队列均无树（t1,t2,carry == nullptr）（应当再次迭代）
            case 1: // 只有this有树（t1有值，t2,carry == nullptr）
                break;
            case 2: // 只有rhs有树（t1 == nullptr, t2有值, carry == nullptr）
                // 将rhs树的根节点并入this后退出
                theTrees[i] = t2;
                rhs.theTrees[i] = nullptr;
                break;
            case 4: // 只有carry有值
                // 此时两个树的节点已合并完，将暂存值carry放入队列后退出
                theTrees[i] = carry;
                carry = nullptr;
                break;
            case 3: // 存在this和rhs，
                // 将当前树合并，存储在carry中后，删除两个树的原根节点（节省空间）
                carry = combineTrees(t1,t2);
                theTrees[i] = rhs.theTrees[i] = nullptr;
                break;
            case 5: // 存在this和carry
                // 此时也相当于合并完，将carry和this合并后退出
                carry = combineTrees(t1,carry);
                theTrees[i] = nullptr;
                break;
            case 6: // 存在rhs和carry
                // 此时也相当于合并完，将carry和rhs合并后退出
                carry = combineTrees(t2,carry);
                theTrees[i] = nullptr;
                break;
            case 7: // 全体树（t1,t2,carry均有值）
                theTrees[i] = carry;
                carry = combineTrees(t1,t2);
                rhs.theTrees[i] = nullptr;
                break;
            }
        }


        /* 删除rhs优先队列 */
        for(auto & root : rhs.theTrees)
            root = nullptr;
        rhs.currentSize = 0;
    }
};